1. Field of the Invention
The present invention relates to domain name system (DNS) servers configured for resolving a query for a location of a requested service by a client device.
2. Description of the Related Art
Domain name system (DNS) servers have enabled users of client devices to locate services on a wide area network (such as the Internet) based on resolving the name of the service to a destination server. Each DNS server is configured for resolving a query for a specified service (i.e., a service specified in the request) according to a prescribed Domain Name System (DNS) described in the Internet Engineering Task Force (IETF) Request for Comments (RFC) 1034 and RFC 1035. For example, a conventional DNS server may be configured for responding to a query by providing a prescribed resolution, or a list of prescribed resolutions. An example of a resolution for a service (e.g., “mail.nowhere.com”) is a service name (e.g., “mail.server1.nowhere.com”), or an explicit IP address (e.g., “10.10.10.10” in IPv4 format).
For example, a client device (e.g., a browser on a user's computer) may send a query to a prescribed DNS server for resolution of the service “mail.nowhere.com”; in response to the query, the DNS server can send a resolution in the form of a name (e.g., “mail.server1.nowhere.com”) or an explicit IP address (e.g., “10.10.10.10”). If the DNS server returns a name, then the host needs to resolve the received name until an explicit IP address is obtained. Note that the client device also may be configured for storing (e.g, as a default entry) an IP address of a name that is recognized as a host identifier.
Hence, the resolution for the service points to a destination, based on the resolution identifying a server (e.g., if the resolution specifies an explicit IP address or a service name recognized by the client device as a host identifier) or another DNS server for more specific resolution.
The DNS server also could return a list of resolutions, where the host computer can connect to any one of the resolutions specified in the list. In this case, a client device can initially attempt to access the first resolution specified in the list; if access is unsuccessful, the client device can attempt to access the second resolution in the list, etc., until connection with one of the resolutions is successful.
A fundamental aspect of conventional DNS servers as described herein is that each of the resolutions supplied by the DNS server are stored statically within (or local to) the DNS server, resulting in “prescribed” resolutions. As described in RFC 1034 (e.g., sec. 2.4), the DNS has Domain Name Space and Resource Records, which are the specifications for a tree structure name space and data associated with the names; each node and leaf of the domain name space tree specifies a set of information, and query operations are attempts to extract specific types of information from a particular set. A query names the domain name of interest and describes the type of resource that is desired. RFC 1034 also describes name servers as holding information about the domain tree's structure and set information. Resolvers are described in RFC 1034 as programs that extract information from name servers in response to client requests.
Hence, the same prescribed resolution (or list of resolutions) is supplied to any requesting client device, regardless of any other consideration. Resolvers rely on the Domain Name Space and Resource Records stored within the name servers by retrieving the resolutions in response to the client requests. If the resolver cannot answer a query from a name server's information, the resolver will pursue the query using referrals from the name server to access other name servers. For example, one resource available on the Internet is referred to as a “NSLOOKUP” command, where a DNS server is sent a query to look up and find IP address information for a prescribed service, for example a domain name. The NSLOOKUP command enables a client device to look up information in the domain name system (DNS) according to RFC 1034, and RFC 1035. For example, sending a NSLOOKUP command for the service “yahoo.com” results in a DNS server executing the resolver to return a list of two IP addresses. Hence, a host computer eventually receives an IP address.
However, the receipt of the same prescribed resolution in the form of a prescribed IP address by multiple client devices does not necessarily result that all the client devices receiving the prescribed IP address will communicate with the same server. In particular, a destination service may employ load sharing to distribute processing across a plurality of servers, providing the appearance to the client devices that the same IP address is being used for the destination service. In particular, a gateway that is advertised as owning the prescribed IP address may forward the client request to one of a plurality of servers. This arrangement, however, is particularly disadvantageous from a network management standpoint when multiple servers are to be used in providing the request of service.
Another form of DNS services that has been implemented has been referred to as “dynamic DNS”, where a router configured for providing Dynamic Host Configuration Protocol (DHCP) IP address assignment to a host network node will update a DNS server with the IP address that has been assigned to the host node. Use of dynamic DNS is particularly beneficial in cases where the host computer, for example a home computer, stores a web page and serves as a web server for a personalized domain name; in this case, the router updates the DNS server with the service name and DHCP assigned IP address. An example of dynamic DNS is provided by the service the DYDNS at the website address “www.dydns.com”. In addition, commercially available Linksys® routers are configured for assigning an IP address according to DHCP, linking the assigned IP address with the user's domain name (or host identifier), and updating the DNS server with the user's assigned IP address and domain name (or host identifier).
Despite the “dynamic DNS” feature offered by devices such as the Linksys® routers, the IP address and corresponding domain name (or host identifier) are still stored by the external device (namely the Linksys® router or the service DYDNS) without any involvement by the DNS server; in other words, the updating technology is implemented external to the DNS server. Hence, the DNS server still relies on a static resolution based solely on retrieval of stored resolutions. Consequently, the DNS server returns the same resolution in response to any query for the specified service, regardless of the nature of the query. Hence, each host node sending a query to a DNS server will receive the same resolution, regardless of identity, location of the host node.
In other words, the mappings between a service name and a destination (e.g., destination host identifier or IP address) that are used to create a resolution are statically configured or programmatically defined by a source that is external to the DNS server: the source is solely responsible for the mapping that creates the resolution accessed by the DNS server.
An additional problem is that the aforementioned DNS servers do not provide any information in the list of resolutions that enable implementation of any policies associated with priority, preference, or load balancing. In particular, the list of resolutions did not provide any information identifying the relative capacity of the respective servers identified in the respective resolutions.
Assume a list of resolutions specifies four servers, and one server has ten times the capacity (10C) of the remaining three servers (1C), such that the total capacity is thirteen units of capacity (13C). In this case, it would be desirable for a given client device to access the larger server 10 out of 13 times (76.9 percent of the time), and any one of the remaining three servers 1 out of 13 times (7.7 percent of the time) in order to optimize load balancing between the servers.
This desirability for implementing a form of load balancing resulted in “DNS SRV”, as specified in RFC 2782, entitled “A DNS RR for specifying the location of services (DNS SRV).” RFC 2782 describes “SRV records” that are generated by a DNS server in response to a DNS query. FIG. 1 is a diagram illustrating a list 10 of resolutions 12 according to RFC 2782. Each resolution 12 includes not only a destination field 14 (e.g., a server name or IP address), but also a corresponding weight 16 and priority 18. The weight 16 and priority 18 enable a client device to participate in performing load balancing based on applying a randomized selection.
In particular, the weight 16 specifies the corresponding capacity (e.g., “1”, “2”, “4”, “9”) of the server (e.g., W1, W2, W4, W9) identified by the destination field (e.g., “W1.nowhere.com”, “W2.nowhere.com”,“W4.nowhere.com”,“W9.nowhere.com”) 14. The priority 18 specifies the order in which the DNS server prefers that the servers specified in the destination field 14 be accessed. In particular, RFC 2782 specifies that a client device must attempt to contact the “target host” (i.e., destination server) with the lowest-numbered priority it can reach; target hosts with the same priority should be tried in an order defined by the weight field.
Hence, if an SRV record 10 specifies multiple resolutions 12, the DNS server relies on the client devices to perform load balancing by selecting between the servers using a random selection algorithm. In other words, the client device is expected to randomly choose the server between the servers based on the specified weight and priority.
Hence, in contrast to conventional DNS, a client having received a SRV record 10 is expected to first select a server from the list of servers having the lowest priority 18; an alternate server having a higher priority 18 can be accessed only if the access attempts to all the servers having the lowest priority 18 were unsuccessful.
FIG. 2 is a diagram illustrating a chart 20 of probabilities 22 that client devices will select the servers 14a, 14b, 14c, and/or 14d according to a particular sequence 24. Assuming equal priority values 18, the RFC 2782 specifies that the client device is to randomly choose from the list 10 according to the weight values 16. As illustrated in FIG. 1, server 14a has a capacity of “1”, the server 14b has twice the capacity of server 14a, the server 14c has four times the capacity of server 14a, and server 14d has nine times the capacity of server 14a. Hence, the total available capacity is 16 units. Hence, based on a randomized selection by a statistically significant number of client devices having received the list 10, the client devices should select, as their first access attempt 26, the servers according to the following probabilities 28: server “W1” 14a  1/16 of the time, server “W2” 14b  2/16 of the time, server “W4” 14c  4/16 of the time, and server “W9” 14d  9/16 of the time. In other words, for a given request by a client device, assuming a truly random selection by the client device, the probability that the client device will select server 14a, 14b, 14c, and 14d on its first access attempt 26 is 6.25%, 12.5%, 25%, and 56.25%, respectively.
If a client device is unsuccessful in reaching a destination 14 (e.g., 14a) specified in the list 10 in its first attempt 26, the client device should select another destination 14 (e.g., 14b) in its second access attempt 30 according to the probabilities 32 in an attempt to receive a response, based on only 15 units of capacity being available among the remaining servers. For example, assuming that the client device in the initial attempted access 26 selected the server “W1” 14a, then in selecting a server for the second request 30 the probability 32 is that the client will select the server “W2” 14b 13.33% of the time, the server “W4” 14c 26.67% of the time, and the server “W9” 14d 60% of the time. If the server from the second selection 30 is unavailable, the client device should perform a third selection 34 according to the probability 36.
Hence, the client device should select the servers according to the sequence 24 according to the corresponding probability 22. As shown in FIG. 2, the highest probability is that the client device will select the servers according to the sequence “W9 W4 W2 W1” (21.43%), and the lowest probability is that the client device will select the servers according to the sequence “W1 W2 W4 W9” (0.26%).
Hence, the probability that a given client device will access the servers 14 specified in the list of resolutions 10 is based on the relative weight values 16 (with respect to probability). Moreover, as described above, the DNS server supplies the same SRV record 10 to all the client devices. Consequently, the weights 16 in the SRV record 10 enable load balancing to be implemented by the client devices, based on the statistical distribution of requests as illustrated in FIG. 2.
However, the method by which the client devices, as a statistical population, perform load balancing is based solely upon implementation of randomization functions in each of the client devices in how each client selects a server. In addition, the same mapping will be returned to every device regardless of any other consideration. Hence, there is an implied trust by the DNS SRV server that the client will apply the DNS SRV algorithm, using random selection, in order to accomplish load balancing. Hence, the choice of load balancing is based solely on reliance of the client device interpreting how to resolve the name according to the list returned.
Hence, any failure in the randomness applied by a group of clients may introduce a bias that affects the random distribution required for even load balancing. In addition, the aforementioned arrangement does not consider that client devices may be configured to disregard random selection, for example in the case of a user that decides to select a server solely based on capacity, thereby disregarding the intended randomness requirements of the client devices to ensure even load balancing.
In summary, there are only two mechanisms for implementing load balancing: relying on client devices to perform random selection of available servers, or an external resource changing the DNS mapping. Although an external resource may be configured for removing from the DNS mapping the identities of failed servers with the respective identities of replacement servers, or change the DNS mappings based on server capacity and performance, the DNS server has no involvement whatsoever in selecting a destination in response to a query; rather, the DNS server merely supplies the stored resolutions associated with the specified service (i.e., the service specified in the query).